#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

static uint64_t two_sum_ways(vector<vector<uint64_t>>& v, int a, int b, int c, int d) {
    uint64_t r1 = v[c][b];
    int i = a;
    while (i < c) 
        r1 += v[i++][b];
    while (i > c)
        r1 += v[i--][b];

    uint64_t r2 = v[a][b];
    i = a;
    while (i < c)
        r2 += v[i++][d];
    while (i > c)
        r2 += v[i--][d];

    return r1 < r2 ? r1 : r2;
}

int main() {
#if 1
    vector<vector<uint64_t>> dp;
    ifstream file ("./82.txt");
    string line;
    while (getline(file, line)) {
        vector<uint64_t> v;
        stringstream ss {line};
        string token;
        while (getline(ss, token, ',')) 
            v.push_back(stoi(token));
        dp.push_back(v);
    }
    file.close();
#else
    vector<vector<uint64_t>> dp {
        {131, 673, 234, 103, 18},
        {201, 96, 342, 965, 150},
        {630, 803, 746, 422, 111},
        {537, 699, 497, 121, 956},
        {805, 732, 524, 37, 331},
    };
#endif
    cout << "matrix: " << dp.size() << " X " << dp[0].size() << ": ";
    for (int j = 1; j < dp[0].size(); ++j) {
        vector<int> vec;
        for (int i = 0; i < dp.size(); ++i) {
            uint64_t sum = dp[i][j-1];
            int jj = j - 1;
            for (int ii = 0; ii < dp.size(); ++ii) {
                uint64_t tmp = two_sum_ways(dp, ii, jj, i, j);
                // cout << tmp << ' ' ;
                if (tmp < sum)
                    sum = tmp;
            }
            vec.push_back(sum);
        }
        for (int i = 0; i < dp.size(); ++i)
            dp[i][j] += vec[i];
    }
    uint64_t ans = dp[0][dp[0].size() - 1];
    for (int i = 0; i < dp.size(); ++i) {
        if (dp[i][dp[0].size() - 1] < ans) {
            ans = dp[i][dp[0].size() - 1];
            // cout << ans << endl;
        }
    }
    cout << ans << endl;
}